Computer systems communicate over networks by establishing and using network connections. For example, when a server wishes to be available for access by client computers over a network, the server can enable its networking processes and components to handle requests that are received from clients. Multiple server applications running on the server can be made available to clients that wish to access the server applications over the network. In one example, a client can contact the server, and the server permits a network connection to be established between client and server.
When using Transmission Control Protocol/Internet Protocol (TCP/IP), for example, a TCP connection is represented by connection information such as a pattern of bits divided into different parameters or fields. For example, a “5-tuple” can be used, which is a set of five parameters that define the connection. For TCP/IP, the 5-tuple is included in the header of each packet sent on a network. The five parameters are the identity of the protocol (in this case, TCP), the source IP address (SA), the source port (SP), the destination IP address (DA), and the destination port (DP) for the packet. From the client's point of view, the source address and source port are at the client end, while the destination address and port are at the server end. The 5-tuple connection information allows network packets of data to be communicated between a server process and a client process in a bi-directional fashion. Each connection has a unique 5-tuple pattern, identified in each packet header.
Before a connection is established between the server and client, the server typically advertises the availability of a connection to a particular process to which clients can connect. For example, the server can set up basic connection information for the connection in the form of a “3-tuple” or a “2-tuple” to indicate the available potential connection. A 3-tuple has three parameters for the identity of the protocol to be used: the destination port of the server, and the destination address of the server for the available connection. The 3-tuple is used when the server has multiple IP addresses (e.g., a multi-homed server), where the particular IP address of the available connection must be specified. At other times, or in other embodiments, only a single IP address is provided for server connections, or the server may not care which one of multiple IP addresses are available for connections. In such cases, a 2-tuple can indicate the available connection, which has two parameters: the identity of the protocol and the destination port.
The server can store 5-tuples, 3-tuples, and 2-tuples in TCP connection tables. When the server receives a packet having a header with connection information (a 5-tuple), the server looks for a matching connection in one of the tables to determine which one of multiple connections should receive the packet. Packets in each connection are eventually provided to a server application at the end of that connection. For example, to establish a connection to the server, a client sends a SYN (synchronization) packet to the server. When the server receives the SYN packet, it looks up a matching 3- or 2-tuple pattern in a table to allow a 3-way handshake process with the client to begin that results in a connection being established (the other fields of the 5-tuple in the packet are ignored). Typically, matches for 3-tuples are searched first, and if none are found, matches for 2-tuples are searched. Once the connection is established, 5-tuple patterns are stored in the direct table and are matched by subsequent packets on that connection.
Existing server systems use different methods to lookup TCP connections to determine where to send incoming packets. In one method, three separate tables are provided, each storing new or existing connections, and a simple hash algorithm is used to look up the connections. One table is used for 5-tuple patterns for existing connections, another table is used for 3-tuple patterns for new connections, and the third table is used for 2-tuple patterns for new connections. Each table requires a different hash key length based on the type of pattern.
A problem with this method is the requirement for storage space in main memory to store three different tables. In addition, the lookup procedure can take a long time in some cases, e.g., when a new connection is looked up on the 3-tuple table and no match is found, a second access to main memory is required to the 2-tuple table, increasing processing time.
Another lookup method allows a single table to be used, and a Longest Prefix Match (LPM) algorithm is implemented. This type of algorithm allows the server to find the best match that fits the most stringent or detailed criteria, and if no match is found, more general criteria are used. A tree structure is used, having nodes and leaves, and thus takes time to process. In addition, the LPM method is a complex algorithm, especially when implemented in hardware, requiring more hardware components such as memory, and thus adds to the expense of the system.
Accordingly, what is needed is an apparatus and method for providing a network connection lookup mechanism that requires less processing and access time and is easier, more efficient, and less expensive to implement. The present invention addresses such a need.